package com.platform.modules.alg.alglib.hdu1251;

public class Hdu1251 {
    private int maxn = 1005;
    private int maxz = 26; // 不同字符个数，例如数字 10，小写字母 26
    int trie[][] = new int[maxn][maxn];
    int cnt[] = new int[maxn]; // 计数器
    int tot; // 下标

    public String output = "";

    // 将字符串 s 插入到字典树中
    void insert(String s) {
        int len = s.length();
        int p = 1;
        for (int i = 0; i < len; i++) {
            int ch = s.charAt(i) - 'a'; // 转换成数字
            if (trie[p][ch] == 0)
                trie[p][ch] = ++tot;// 记录下标
            p = trie[p][ch];
            cnt[p]++; // 统计有多少个单词经过
        }
    }

    int query(String s) {
        int len = s.length(), p = 1;
        for (int i = 0; i < len; i++) {
            int ch = s.charAt(i) - 'a'; // 转换成数字
            p = trie[p][ch];
            if (p == 0)
                return 0;
        }
        return cnt[p];
    }

    public String cal(String input) {
        String s;
        tot = 1;
        String[] line = input.split("\n");
        int count = 0;
        while (true) {
            s = line[count++];
            if (s.length() == 0)
                break;
            insert(s);
        }
        while (true) {
            if (count == line.length)
                break;
            s = line[count++];
            if (s.length() == 0)
                break;
            output += query(s) + "\n";
        }
        return output;
    }
}
